#include <stdio.h>
#include <stdlib.h>
// 折半查找(二分查找)
// 前提是数组有序
int *count = (int *)malloc(sizeof(int)); // 计数器，纪录查找次数
int binary_search(int arr[], int len, int value){
    int low = 0; // 低位索引
    int high = len - 1; // 高位索引
    int mid = (low + high) / 2; // 中间索引，向下取整
    *count = 0; // 初始化查找次数为0
    while (low <= high) { // 当低位索引小于等于高位索引时循环
        (*count)++; // 每次循环查找次数加1
        if (arr[mid] == value) { // 如果中间元素等于目标值，返回中间索引
            printf("查找次数: %d\n", *count);
            return mid;
        } else if (arr[mid] < value) { // 如果中间元素小于目标值，说明目标值在右半部分
            low = mid + 1; // 低位索引加1
        } else { // 如果中间元素大于目标值，说明目标值在左半部分
            high = mid - 1; // 高位索引减1
        }
        mid = (low + high) / 2; // 重新计算中间索引
    }
    return -1; // 未找到目标元素，返回-1
}

int main() {
    int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150, 160, 170, 180, 190, 200};
    int len = sizeof(arr) / sizeof(arr[0]); // 计算数组长度
    int value = 71;
    int index = binary_search(arr, len, value);
    if (index != -1) {
        printf("元素 %d 在数组中的索引为: %d\n", value, index);
    } else {
        printf("查找次数: %d\n", *count);
        printf("元素 %d 不在数组中\n", value);
    }
    free(count);
    return 0;
}